57. Insert Interval (Linkedin Hard)(Java)
作者:JY
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
思路：
这道题给出非重叠区间，以及待插入区间，需要我们insert或者mege进去，有重叠和不重叠两种情况，因此我们需要分情况讨论。当区间不重叠时，我们将待插入区间直接插入到对应的位置，当重叠情况出现时，我们需要更新新区间的范围以便包含所有重叠，而且最后处理的时候还需要删除原区间集中所有和新区间重叠的区间，然后插入新区间即可。
题解1: Comparator
新建一个链表res, 引入Comparator类,若newInterval与当前interval没有交集，则按照先后次序加入newInterval和当前interval，加入剩下的interval, 返回res。若newInterval与当前interval有交集，合并成为新的newInterval，处理interval。未返回res，此时newInterval为最后一个interval，装入res。return res。
Time Complexity：O(nlogn)
Space Complexity：O(n)
代码如下：
class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new ArrayList<>();
for(Interval i : intervals) {
if( i.start <= newInterval.end && i.end >= newInterval.start) {
newInterval.start = Math.min(i.start, newInterval.start);
newInterval.end = Math.max(i.end, newInterval.end);
} else {
res.add(i);//不存在gap，或者合并区间与后面区间没有gap，添加到结果集
}
}
res.add(newInterval);//将最后一个区间加入到结果集
Collections.sort(res, new Comparator<Interval>() {//对原区间集合排序
public int compare(Interval a, Interval b) {
return a.start - b.start;//使用匿名类实现对区间的排序
}
});
return res;
}
}
题解2,Using index
遍历所有的区间，如果新区间的末尾小于当前区间的开头，循环结束。如果插入区间的开头大于当前区间的末尾，不产生重叠区域。如果新区间和当前区间有重叠，则更新新区间的开头为两者最小值，新区间的末尾为两者最大值，重叠数加1。指针移向下一个区间。如果重叠数大于0，则删除掉所有的重叠区间， return新生成的interval。
Time Complexity：O(n)
Space Complexity：O(n)
代码如下：
public class Solution {
public List<Interval> insert(List<Interval> intList, Interval newInterval) {
List<Interval> res = new LinkedList<>();
int i= 0;//从第一个点开始遍历
int n=intList.size();
int nStart=newInterval.start;//定义新的interval的起点和终点的初值并初始化
int nEnd=newInterval.end;
while(i<n&&intList.get(i).end<newInterval.start){//当前看到的区间的终点小于要插入interval的起点
res.add(intList.get(i));//把当前不相关的interval加入至数组中
i++;
}if(i==n){
res.add(newInterval);
return res;//前面都是有效线段，在最后加入新的线段
}
// 如果找到合适的起点线段，则更新nStart的值
nStart = Math.min(intList.get(i).start, newInterval.start);
while(i<n&&intList.get(i).start<=newInterval.end){
nEnd=Math.max(newInterval.end,intList.get(i).end);
i++;
}
res.add(new Interval(nStart,nEnd));
while(i<n){
// add newInterval at the right place
res.add(intList. get(i++));
}
return res;
}
}
题解3:二分查找法
基本思想是将n个元素分成大致相等的两部分，去a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；
总共有n个元素，之后就是n,n/2,n/4,…n/2k，其中k就是循环的次数，由于你n/2k取整后>=1
即令n/2^k=1可得k=log2n,（是以2为底，n的对数）
Time Complexity:O(logn)
Space Complexity:O(n)
代码如下：
class Solution {
public int find(List<Interval> intervals, int start) {
int i = 0, j = intervals.size()-1;
while (i<=j) {
int m = (i+j)/2;
if (intervals.get(m).start < start) i = m + 1;
else j = m - 1;
}
return i; //the first element in therange of intervals.get(i).start >= start
}
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new ArrayList<>();
int location = find(intervals, newInterval.start);
for(int i=0; i<location; i++) res.add(intervals.get(i));
if (location>0 && newInterval.start <= res.get(location-1).end) {
res.get(location-1).end = Math.max(res.get(location-1).end, newInterval.end);
} else {
res.add(newInterval);
}
while (location < intervals.size() && intervals.get(location).start <= res.get(res.size()-1).end) {
res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end, intervals.get(location).end);
location ++;
}
for(int i=location; i<intervals.size(); i++) res.add(intervals.get(i));
return res;
}
}
